package com.yohann.algorithm;

/**
 * <p>
 *
 * </p>
 *
 * @author Yohann
 * @since 2020/9/26
 */
public class Sort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 6, 11, -1, 12, 0,-1};
        int[] ints = quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    //希尔排序
    public static int[] shellSort(int[] arr) {
        int temp = 0;
        int index = 0;

        //步长每次除2
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第二组开始
            for (int i = gap; i < arr.length; i++) {
                index = i;
                temp = arr[i];

                //前一个数位置>=0 当前数与同一组前面的数进行插入排序 即每一组数进行插入排序
                while (index - gap >= 0 && temp < arr[index - gap]) {
                    arr[index] = arr[index - gap];
                    index -= gap;
                }

                arr[index] = temp;
            }
        }

        return arr;
    }

    //快速排序
    public static int[] quickSort(int[] arr, int left, int right)  {
        int l = left;
        int r = right;

        int pivot = arr[(left + right) / 2];
        int temp = 0;

        while (l < r) {
            while (arr[l] < pivot) {
                l += 1;
            }
            while (arr[r] > pivot) {
                r -= 1;
            }

            if (l >= r) {
                break;
            }

            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            if (arr[l] == pivot) {
                r -= 1;
            }
            if (arr[r] == pivot) {
                l += 1;
            }

            if (left < r) {
                quickSort(arr, left, r);
            }

            if (right < l) {
                quickSort(arr, l, right);
            }
        }

        return arr;
    }
}
